/**
//给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。 
//
// 
//
// 示例 : 
//给定二叉树 
//
//           1
//         / \
//        2   3
//       / \     
//      4   5    
// 
//
// 返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。 
//
// 
//
// 注意：两结点之间的路径长度是以它们之间边的数目表示。 
// Related Topics 树 深度优先搜索 二叉树 👍 845 👎 0

*/

package com.xixi.dataStructure.tree.binaryTree;

import com.xixi.dataStructure.tree.TreeNode;

public class ID00543DiameterOfBinaryTree {
public static void main(String[] args) {
Solution solution = new ID00543DiameterOfBinaryTree().new Solution();
}


//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

    int maxDiameter = 0;
    public int diameterOfBinaryTree(TreeNode root) {

        findDeepthOfTree(root);

        return maxDiameter;
    }

    public int findDeepthOfTree(TreeNode node){
        if(node == null) return 0;
        //分别找到左右子树的深度；
        int leftDepth = findDeepthOfTree(node.left);
        int rightDepth = findDeepthOfTree(node.right);
        //判断左右子树的最大深度之和是否超过了当前的最大直径。
        maxDiameter = Math.max(maxDiameter, leftDepth+rightDepth);

        //返回的是当前树的最大深度
        return Math.max(leftDepth, rightDepth) + 1;

    }

}
//leetcode submit region end(Prohibit modification and deletion)




}